//
// RS Game Framework
// Copyright © 2009 Jedd Haberstro
// jhaberstro@gmail.com
// 
// $Id:
//

#ifndef RS_LOCKFREESTACK_HPP
#define RS_LOCKFREESTACK_HPP

#include "rs/Atomic.hpp"
#include "rs/MetaFacilities.hpp"
#include "rs/Portability.hpp"

namespace rs
{
    namespace concurrency
    {
        // Game programming gems 6 stack implementation
        // Not 64-bit safe - assumes 32 bit wide pointers
        template< typename T >
        class LockFreeStack
        {
        public:
            
            struct Cell
            {
                Cell()
                : next(0) {
                }
                
                Cell(T value)
                : value(value),
                  next(0) {
                }
                
                T value;
                Cell* volatile next;
            };
            
        public:
            
            LockFreeStack();
            
            void Push(Cell* node);
            
            Cell* Pop();
            
            Int32 GetSize() const;
            
        private:
            
            LockFreeStack(LockFreeStack const& other);
            LockFreeStack& operator=(LockFreeStack const& other);
            
        private:
            
            Cell* volatile head_;
            UInt32 volatile pops_;
            Int32 volatile size_;
        };
        
        
        template< typename T >
        inline LockFreeStack< T >::LockFreeStack()
        : head_(0),
          pops_(0),
          size_(0) {
              RS_STATIC_ASSERT(sizeof(head_) == 4, head_is_not_sizeof_4);
        }
        
        template< typename T >
        void LockFreeStack< T >::Push(Cell* node) {
            while (true) {
                node->next = head_;
                if (atomic::CompareSwap(reinterpret_cast< UInt32 volatile* >(&head_), reinterpret_cast< UInt32 >(node->next), reinterpret_cast< UInt32 >(node))) {
                    break;
                }
            }
            
            atomic::AddFetch(&size_, 1);
        }
        
        template< typename T >
        typename LockFreeStack< T >::Cell* LockFreeStack< T >::Pop() {
            while (true) {
                Cell* head = head_;
                UInt32 pops = pops_;
                
                if (head == 0) {
                    return 0;
                }
                
                Cell* next = head->next;
                Int64 oldValue = reinterpret_cast< UInt64 >(head) | (static_cast< UInt64 >(pops) << 32);
                Int64 newValue = reinterpret_cast< UInt64 >(next) | (static_cast< UInt64 >(pops + 1) << 32);
                if (atomic::CompareSwap(reinterpret_cast< UInt64 volatile* >(&head_), oldValue, newValue)) {
                    atomic::AddFetch(&size_, -1);
                    return head;
                }
            }
        }
        
        template< typename T >
        Int32 LockFreeStack< T >::GetSize() const {
            return size_;
        }
    }
}

#endif // RS_LOCKFREESTACK_HPP
